/*
 * com.future CO.,ltd.
 */

package com.future;

/**
 * Description: 大厂刷题班4
 * 给定三个字符串 s1、s2、s3，请你帮忙验证 s3 是否是由 s1 和 s2 交错 组成的。
 * <p>
 * 两个字符串 s 和 t 交错 的定义与过程如下，其中每个字符串都会被分割成若干 非空 子字符串：
 * <p>
 * s = s1 + s2 + ... + sn
 * t = t1 + t2 + ... + tm
 * |n - m| <= 1
 * 交错 是 s1 + t1 + s2 + t2 + s3 + t3 + ... 或者 t1 + s1 + t2 + s2 + t3 + s3 + ...
 * 注意：a + b 意味着字符串 a 和 b 连接。
 * <p>
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/interleaving-string
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 *
 * @Author: future
 * @Date:2022/3/25:23:31
 */
public class Solution_97_IsInterleave {


    public static void main(String[] args) {
        //String s1 = "aabcc", s2 = "dbbca", s3 = "aadbbcbcac";
        //String s1 = "aabcc", s2 = "dbbca", s3 = "aadbbcbcac";
        String s1 = "a", s2 = "", s3 = "a";
        System.out.println(isInterleave(s1, s2, s3));
    }

    public static boolean isInterleave(String s1, String s2, String s3) {
        if (s1 == null || s2 == null || s3 == null) {
            return false;
        }
        int n1 = s1.length();
        int n2 = s2.length();
        int n3 = s3.length();
        if (n1 + n2 != n3) {
            return false;
        }
        char[] str1 = s1.toCharArray();
        char[] str2 = s2.toCharArray();
        char[] str3 = s3.toCharArray();
        /**
         * 这里的0,1...是指长度为0,1
         * eg:
         * dp[1][0],指的是s1长度为1，s2长度为0（不选择s2）
         */
        boolean[][] dp = new boolean[n1 + 1][n2 + 1];
        dp[0][0] = true;
        for (int i = 1; i <= n1; i++) {
            if (str3[i - 1] != str1[i - 1]) {
                break;
            }
            dp[i][0] = true;
        }
        for (int j = 1; j <= n2; j++) {
            if (str3[j - 1] != str2[j - 1]) {
                break;
            }
            dp[0][j] = true;
        }
        /**
         * 这里的i,j是指长度，而不是下标
         * i=0,说明不选择s1，i=1,选择s1长度为1，即s1位置为0的下标
         * .....
         */
        for (int i = 1; i <= n1; i++) {
            for (int j = 1; j <= n2; j++) {
                /**
                 * 1、
                 * str1第i-1位跟str3相等，
                 * 且str1从0...(i-1),str2从0...j，都能使str3从0...((i-1)+j-1)成立
                 */
                if ((str1[i - 1] == str3[i + j - 1] && dp[i - 1][j]) ||
                        /**
                         * 2、
                         * str2第j-1位跟str3相等，
                         * 且str1从0...i,str2从0...j-1，都能使str3从0...(i+(j-1)+1)成立
                         */
                        (str2[j - 1] == str3[i + j - 1] && dp[i][j - 1])) {
                    dp[i][j] = true;
                }
            }
        }
        return dp[n1][n2];
    }
}
